# -*- coding:utf-8 -*- 
__date__ = '2022/6/24 5:14 下午'

'''
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
'''


# 二分查找算法
# ls: low--->height
class Solution:
  def binary_search(self, ls, target):
    left, right = 0, len(ls) - 1
    while left <= right:
      mid = (left + right) // 2
      if ls[mid] == target:
        return mid
      elif ls[mid] > target:
        right = mid - 1
      else:
        left = mid + 1
    return -1

  def binary_search1(self, ls, left, right, target):
    if left > right:
      return -1
    mid = (left + right) // 2
    if ls[mid] == target:
      return mid
    elif ls[mid] > target:
      return self.binary_search1(ls, left, mid - 1, target)
    else:
      return self.binary_search1(ls, mid + 1, right, target)


if __name__ == '__main__':
  solution = Solution()
  ls = [-1, 0, 3, 5, 9, 12]
  position = solution.binary_search(ls, 12)
  print(position)
  position1 = solution.binary_search1(ls, 0, len(ls) - 1, 12)
  print(position1)
